package 力扣_树算法.树与链表;

import java.util.ArrayList;
import java.util.List;

/**897. 递增顺序搜索树
 * @author zx
 * @create 2022-04-15 8:57
 */
public class Num897 {
    /**
     * 这个思路的题做完后,再去做(剑指 Offer 36. 二叉搜索树与双向链表)
     *
     * 中序遍历的时候,修改节点指向就可以实现.当我们遍历到一个节点时,把它的左孩子设为空,将其本身作为
     *      上一个遍历到的节点的右孩子.递归遍历的过程中,由于递归函数的调用栈保存了节点的引用,因此上述操作可以实现.
     */
    /**
     * 非虚拟头节点版
     */
    TreeNode prev = null;
    TreeNode head = null;
    public TreeNode increasingBST(TreeNode root) {
        inOrder(root);
        return head;
    }
    private void inOrder(TreeNode root){
        if(root == null){
            return;
        }
        inOrder(root.left);
        if(prev != null){
            prev.right = root;
        }else{
            head = root;//确定头节点
        }
        root.left = null;
        prev = root;
        inOrder(root.right);
    }

    /**
     * @return 虚拟头节点版
     */
    //TreeNode prev = null;
    public TreeNode increasingBST2(TreeNode root) {
        TreeNode dummy = new TreeNode(-1);
        prev = dummy;
        inOrder(root);
        return dummy.right;
    }
    private void inOrder2(TreeNode root){
        if(root == null){
            return;
        }
        inOrder(root.left);
        //修改节点指向
        prev.right = root;
        root.left = null;
        prev = prev.right;
        inOrder(root.right);
    }
}
class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode() {}
    TreeNode(int val) { this.val = val; }
    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}
